// 思路1，递归

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}
function insertIntoBST(root, val) {
    if (!root) {
        return new TreeNode(val)
    }
    if (root.val < val) {
        root.right = insertIntoBST(root.right, val)
    }
    if (root.val > val) {
        root.left = insertIntoBST(root.left, val)
    }
    return root
}

const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
        right: {
            val: 3.5,
            left: {
                val: 3.1
            }
        },
    },
    right: {
        val: 6,
    },
};

console.log(insertIntoBST(root, 2.5))